package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-13 13:45
 **/
public class LeetCode301 {

    public List<String> removeInvalidParentheses(String s) {

        //需要移除的左括号数量
        int lremove = 0;
        //需要移除的右括号数量
        int rremove = 0;

        //遍历到'('时,左括号数量+1
        //遍历到')'时,左括号数量不为0,则-1,否则右括号数量+1
        //遍历结束,lremove和rremove就是左括号和右括号需要删除的数量
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == '(') {
                ++lremove;
            } else if (s.charAt(i) == ')'){
                if (lremove > 0) {
                    --lremove;
                } else {
                    ++rremove;
                }
            }
        }

        List<String> res = new ArrayList<>();
        backtrack(s, lremove, rremove, 0, res);
        return res;
    }

    void backtrack(String s, int lremove, int rremove, int start, List<String> res) {
        if (lremove == 0 && rremove == 0) {
            //如果是合法括号字符串,添加到结果集中
            if (isValid(s)) {
                res.add(s);
            }
            return;
        }

        for (int i = start; i < s.length(); ++i) {
            //我们在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 "(((())"，
            // 去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 "((())"，
            // 因此我们在尝试搜索时，只需去掉一个左括号进行下一轮搜索，不需要将前四个左括号都尝试一遍。
            if (i != start && s.charAt(i) == s.charAt(i - 1)) {
                continue;
            }

            // 如果剩余的字符无法满足去掉的数量要求，直接返回
            if (lremove + rremove > s.length() - i) {
                return;
            }

            // 尝试去掉一个左括号
            if (lremove > 0 && s.charAt(i) == '(') {
                backtrack(s.substring(0, i) + s.substring(i + 1), lremove - 1, rremove, i, res);
            }

            // 尝试去掉一个右括号
            if (rremove > 0 && s.charAt(i) == ')') {
                backtrack(s.substring(0, i) + s.substring(i + 1), lremove, rremove - 1, i, res);
            }
        }




    }

    /**
     * 判断字符串是否为合法括号
     */
    boolean isValid(String s) {
        int cnt = 0;

        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++cnt;
            } else if (s.charAt(i) == ')') {
                --cnt;
                if (cnt < 0) {
                    return false;
                }
            }
        }

        return cnt == 0;
    }
}
